package leetcode71_80;

import org.junit.Test;

/**
 * @author shhjiang_001
 * @create 2020-06-22 11:14
 */

        /*
        给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
        此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
        注意:
        不能使用代码库中的排序函数来解决这道题。
        示例:

        输入: [2,0,2,1,1,0]
        输出: [0,0,1,1,2,2]
        */

public class Solution75 {
    public void sortColors1(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            for (int j = i; j < length-1; j++) {
                if (nums[j] >= nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }

            }
        }

    }
    // 三路快排？
    public void sortColors(int[] nums) {
        int lt = -1;
        int gt = nums.length;
        int i = 0;
         while (i < gt){
             if (nums[i] == 1){
                 i++;
             }else if (nums[i] == 0){
                 // 索引对应元素为0，与左指针元素交换
                 lt++;
                 swap(nums,lt,i);
                 i++;
             }else {
                 // 索引对应的元素为2，与右指针元素进行交换
                 gt--;
                 swap(nums,gt,i);
             }
         }


    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    @Test
    public void test(){
        sortColors(new int[]{2,0,2,1,1,0});
    }
}
